﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.Struct
{
    public class BinTree<TData>
    {
        public TData Data;

        public BinTree<TData> LeftNode
        {
            get;
            set;
        }

        public BinTree<TData> RightNode
        {
            get;
            set;
        }
    }

    public static class BinTreeHelper
    {
        public static void BeforeIterateRecursion<TData>(BinTree<TData> tree,Action<BinTree<TData>> action)
        {
            if (null != tree)
            {
                action(tree);
                BeforeIterateRecursion(tree.LeftNode, action);
                BeforeIterateRecursion(tree.RightNode, action);
            }
        }

        public static void MidIterateRecursion<TData>(BinTree<TData> tree, Action<BinTree<TData>> action)
        {
            if (null != tree)
            {
                MidIterateRecursion(tree.LeftNode, action);
                action(tree);
                MidIterateRecursion(tree.RightNode, action);
            }
        }

        public static void AfterIterateRecursion<TData>(BinTree<TData> tree, Action<BinTree<TData>> action)
        {
            if (null != tree)
            {
                AfterIterateRecursion(tree.LeftNode, action);
                AfterIterateRecursion(tree.RightNode, action);
                action(tree);
            }
        }

        public static void BeforeIterateNonRecursion<TData>(BinTree<TData> tree, Action<BinTree<TData>> action)
        {
            Stack<BinTree<TData>> stack = new Stack<BinTree<TData>>(1000);

            BinTree<TData> currentNode = tree;

            while (null != currentNode || !stack.IsEmpty())
            {
                while (null != currentNode)
                {
                    action(currentNode);
                    stack.Push(currentNode);
                    currentNode = currentNode.LeftNode;
                }
                if (!stack.IsEmpty())
                {
                    currentNode = stack.Pop().RightNode;
                }
            }
        }

        public static void MidIterateNonRecursion<TData>(BinTree<TData> tree, Action<BinTree<TData>> action)
        {
            Stack<BinTree<TData>> stack = new Stack<BinTree<TData>>(1000);

            BinTree<TData> currentNode = tree;

            while (null != currentNode || !stack.IsEmpty())
            {
                while (null != currentNode)
                {
                    stack.Push(currentNode);
                    currentNode = currentNode.LeftNode;
                }

                if (!stack.IsEmpty())
                {
                    currentNode = stack.Pop();
                    action(currentNode);
                    currentNode = currentNode.RightNode;
                }
            }
        }

        public static void AfterIterateNonRecursion<TData>(BinTree<TData> tree, Action<BinTree<TData>> action)
        {
            Stack<BinTree<TData>> stack = new Stack<BinTree<TData>>(1000);

            BinTree<TData> currentNode = null;

            BinTree<TData> preNode = null;
            stack.Push(tree);
            while (!stack.IsEmpty())
            {
                currentNode = stack.Top();

                if ((null == currentNode.LeftNode && null == currentNode.RightNode) ||
                    (preNode == currentNode.LeftNode || preNode == currentNode.RightNode))
                {
                    action(currentNode);
                    stack.Pop();
                    preNode = currentNode;
                }
                else
                {
                    if (null != currentNode.RightNode)
                    {
                        stack.Push(currentNode.RightNode);
                    }
                    if (null != currentNode.LeftNode)
                    {
                        stack.Push(currentNode.LeftNode);
                    }
                }
            }
        }

        public class HelpeStruct<TData>
        {
            public BinTree<TData> TreeNode;
            public bool IsFirst;
        }

        public static void AfterIterateNonRecursion1<TData>(BinTree<TData> tree, Action<BinTree<TData>> action)
        {
            Stack<HelpeStruct<TData>> stack = new Stack<HelpeStruct<TData>>(1000);

            BinTree<TData> current = tree;

            HelpeStruct<TData> help = null;

            while (null != current || !stack.IsEmpty())
            {
                while (null != current)
                {
                    help = new HelpeStruct<TData>() { IsFirst =true,TreeNode = current };
                    stack.Push(help);
                    current = current.LeftNode;
                }

                if (!stack.IsEmpty())
                {
                    help = stack.Pop();
                    if (help.IsFirst)
                    {
                        stack.Push(help);
                        help.IsFirst = false;
                        current = help.TreeNode.RightNode;
                    }
                    else
                    {
                        action(help.TreeNode);
                        current = null;
                    }
                }
            }
        }
    }
}
